【题解】 [HAOI2012]高速公路 线段树 luoguP2221 | Qiuly's blog!

【题解】 [HAOI2012]高速公路 线段树 luoguP2221

Posted on | In | Comments:

$3$ 月份的最后一篇题解了呢……明天就属于 $4$ 月了，离省选不远了…$QwQ$…

发现窝真的很制杖，我们先来聊聊刚开始窝的想法。

我画了画图，然后发现，对于最后答案的分母(不是最简)，是这个序列中这些数的值(废话)，然后发现了每个点的出现次数，然后线段树维护求和。发现效率很低于是试图将出现次数般到二维平面上，然后曼哈顿距离转切比雪夫距离然后二维树状数组维护然后 $WA$ 了然后弃疗。

你可能认为窝很傻对吧？

嗯对窝是挺傻的。

正解是线段树，没猜错，但是和什么二维树状数组有什么关系

我们考虑区间中的一个点 $i$ ，权值为 $v_i$ 。然后我们观察当前询问区间中有多少子区间包含了 $v_i$ ，这个个数就是点 $i$ 做出的贡献。现在我们来考虑怎么计算这个包含了 $i$ 的子区间个数。

可以发现，我们从 $i$ 向左扩展若干个点，然后又向右扩展若干个点，这样子一来就成了一个包含了 $i$ 子区间。这个就很好计算了，答案显然为 $(i-l)\times(r-i)$ 。然后还要算进没有向左/右扩展的情况，并且算上权值，最终 $i$ 造成的贡献显然为：

那么我们将式子拆开可以得到：

其中 $l,r$ 为当前询问区间，这个是可以直接算出的。我们发现我们需要维护的就是 $v_i\ ,\ v_ii\ ,\ v_ii^2$ 三个值，用线段树维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+2;
const int inf=1e9+9;

int n,m;
char op[2];

namespace OI {
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
        while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
        if(flag)x=-x;
    }
    template <typename _Tp> _Tp gcd(_Tp x,_Tp y) {
        return y?gcd(y,x%y):x;
    }
}using namespace OI;

struct Segment_Tree {
    #define mid ((l+r)>>1)
    #define LS(x) ((x)<<1)
    #define RS(x) ((x)<<1|1)

    ll ans1,ans2,ans3;
    ll sum1[N<<2],sum2[N<<2],sum3[N<<2];
    ll tag[N<<2],suq[N<<2],rle[N<<2],len[N<<2];

    void build(ll x,ll l,ll r) {
        if(l==r) {
            len[x]=1,suq[x]=l,rle[x]=l*l;
            return;
        }
        build(LS(x),l,mid),build(RS(x),mid+1,r);
        len[x]=len[LS(x)]+len[RS(x)];
        suq[x]=suq[LS(x)]+suq[RS(x)],
        rle[x]=rle[LS(x)]+rle[RS(x)];
    }
    void pushdown(ll x,ll l,ll r) {
        ll k=tag[x];tag[x]=0;
        sum1[LS(x)]+=len[LS(x)]*k,sum1[RS(x)]+=len[RS(x)]*k;
        sum2[LS(x)]+=suq[LS(x)]*k,sum2[RS(x)]+=suq[RS(x)]*k;
        sum3[LS(x)]+=rle[LS(x)]*k,sum3[RS(x)]+=rle[RS(x)]*k;
        tag[LS(x)]+=k,tag[RS(x)]+=k;
    }
    void update(ll x,ll l,ll r,ll L,ll R,ll v) {
        if(L<=l&&r<=R) {
            tag[x]+=v;
            sum1[x]+=len[x]*v;
            sum2[x]+=suq[x]*v;
            sum3[x]+=rle[x]*v;
            return;
        }
        if(tag[x])pushdown(x,l,r);
        if(L<=mid)update(LS(x),l,mid,L,R,v);
        if(R>mid)update(RS(x),mid+1,r,L,R,v);
        sum1[x]=sum1[LS(x)]+sum1[RS(x)];
        sum2[x]=sum2[LS(x)]+sum2[RS(x)];
        sum3[x]=sum3[LS(x)]+sum3[RS(x)];
    }
    void query(ll x,ll l,ll r,ll L,ll R) {
        if(L<=l&&r<=R) {
            ans1+=sum1[x],ans2+=sum2[x],ans3+=sum3[x];
            return;
        }
        if(tag[x])pushdown(x,l,r);
        if(L<=mid)query(LS(x),l,mid,L,R);
        if(R>mid)query(RS(x),mid+1,r,L,R);
    } 
}T;

int main() {
    IN(n),IN(m);
    T.build(1,1,n);
    for(int i=1;i<=m;++i) {
        scanf("%s",op);
        ll l,r;IN(l),IN(r);--r;
        ll v;
        if(op[0]=='C') IN(v),T.update(1,1,n,l,r,v);
        else if(op[0]=='Q') {
            T.ans1=T.ans2=T.ans3=0;
            T.query(1,1,n,l,r);
            ll res1=T.ans1,res2=T.ans2,res3=T.ans3;
            ll ans=(r-l+1-l*r)*res1+(r+l)*res2-res3;
            ll len=(r-l+1)*(r-l+2)/2;
            ll esw=gcd(ans,len);
            printf("%lld/%lld\n",ans/esw,len/esw);
        }
    }
    return 0;
}

本文标题:【题解】 [HAOI2012]高速公路 线段树 luoguP2221

文章作者:Qiuly

发布时间:2019年03月31日 - 00:00

最后更新:2019年03月31日 - 19:16

原始链接:http://qiulyblog.github.io/2019/03/31/[题解]luoguP2221/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。